# 二叉树
class Node:
	def __init__(self,data):
		self.data = data
		self.lchild = None
		self.rchild = None

a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
e = Node('E')
f = Node('F')
g = Node('G')
h = Node('H')
i = Node('I')

a.lchild = b
a.rchild = c
b.lchild = d
b.rchild = e
e.lchild = h
e.rchild = i
c.lchild = f
c.rchild = g


def pre_order(root):
	if root:
		print(root.data,end=',')  # pre_order先序遍历
		pre_order(root.lchild) 
		print(root.data,end=',')  # in_order中序遍历
		pre_order(root.rchild)
		print(root.data,end=',')  # after_order后序遍历


# pre_order(a)
# 层次遍历
def leavel_order(root):
	queue = []
	queue.append(root)
	while queue:
		next = queue.pop(0)
		print(next.data)
		if next.lchild:
			queue.append(next.lchild)
		if next.rchild:
			queue.append(next.rchild)

def leavel_order(root):
	stack = []
	stack.append(root)
	flag = 0
	for i in stack:
		if stack[flag].lchild:
			stack.append(stack[flag].lchild)
			
		if stack[flag].rchild:
			stack.append(stack[flag].rchild)
		flag += 1
	print([i.data for i in stack])
# leavel_order(a)


# 二叉搜索树（父亲比左孩子大比右孩子小）中序遍历一定是升序的
class BiTreeNode:
	def __init__(self,data):
		self.data = data
		self.lchild = None
		self.rchild = None
		self.parent = None

class BST:
	def __init__(self, li=None):
		self.root = None
		if li:
			for val in li:
				self.insert_no_rec(val)

	# 插入(递归)
	def insert(self, node, val):
		if not node:
			node = BiTreeNode(val)
		elif val < node.data:
			node.lchild = self.insert(node.lchild, val)
			node.lchild.parent = node
		elif val > node.data:
			node.rchild = self.insert(node.rchild, val)
			node.rchild.parent = node
		return node

	# 插入（非递归）
	def insert_no_rec(self, val):
		p = self.root
		if not p:
			self.root = BiTreeNode(val)  # 空树
			return
		while True:
			if val < p.data:
				if p.lchild:
					p = p.lchild
				else:  # 左孩子不存在
					p.lchild = BiTreeNode(val)
					p.lchild.parent = p
					return
			elif val > p.data:
				if p.rchild:
					p = p.rchild
				else:  # 右孩子不存在
					p.rchild = BiTreeNode(val)
					p.rchild.parent = p
					return
			else:
				return

	# 查找(递归)
	def query(self, node, val):
		if not node:
			return None
		if val == node.data:
			return node
		elif val > node.data:
			self.query(node.rchild, val)
		else:
			self.query(node.lchild, val)


	# 查找（非递归）
	def query_no_rec(self, val):
		p = self.root
		while p:
			if val == p.data:
				return p
			elif val > p.data:
				p = p.rchild
			else:
				p = p.lchild
		return None

	# 删除
	# 情况1：node是叶子节点
	def __remove_node_1(self, node):
		if not node.parent:
			self.root = None
		if node == node.parent.lchild:  # node是它父亲的左孩子
			node.parent.lchild = None
		else:  # 右孩子
			node.parent.rchild = None

	# 情况2：node只有一个左孩子
	def __remove_node_2_1(self, node):
		if not node.parent:
			self.root = node.lchild
			node.lchild.parent = None
		elif node == node.parent.lchild: # 它是它父亲的左孩子
			node.parent.lchild = node.lchild
			node.lchild.parent = node.parent
		else: # 它是它父亲的右孩子
			node.parent.rchild = node.lchild
			node.lchild.parent = node.parent

	# 情况2：node只有一个右孩子
	def __remove_node_2_2(self, node):
		if not node.parent:
			self.root = node.rchild
			node.lchild.parent = None
		elif node == node.parent.lchild: # 它是它父亲的左孩子
			node.parent.lchild = node.rchild
			node.rchild.parent = node.parent
		else: # 它是它父亲的右孩子
			node.parent.rchild = node.rchild
			node.rchild.parent = node.parent

	def delete(self, val):
		if self.root:  # 不是空树
			node = self.query_no_rec(val)
			if not node:  # val不存在
				return False
			if not node.lchild and not node.rchild:  # 情况1：叶子节点
				self.__remove_node_1(node)
			elif not node.rchild: # 情况2.1： 只有一个左孩子
				self.__remove_node_2_1(node)
			elif not node.lchild: # 情况2.2： 只有一个右孩子
				self.__remove_node_2_2(node)
			else: # 情况3： 两个孩子都有
				min_node = node.rchild
				while min_node.lchild:
					min_node = min_node.lchild  # 拿到右孩子中最小的左孩子
				node.data = min_node.data  # 赋值
				# 删除min_node
				if min_node.rchild: # 只有一个右孩子
					self.__remove_node_2_2(min_node)
				else:  # 叶子节点
					self.__remove_node_1(min_node)

	# 中序遍历
	def in_order(self, root):
		if root:
			self.in_order(root.lchild) 
			print(root.data,end=',')  # in_order中序遍历
			self.in_order(root.rchild)


import random
li = [1,3,2,4,5,7,6]
random.shuffle(li)
tree = BST(li)
tree.in_order(tree.root)
print('')

tree.delete(2)
tree.in_order(tree.root)


# AVL树（平衡二叉树）
# 插入 右右-左旋  左左-右旋  左右-先左旋再右旋  右左-先右旋再左旋






















